package com.leetcodehot.problems;

import java.util.Arrays;

public class problems2517 {
    /**
     * 给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
     * <p>
     * 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
     * <p>
     * 返回礼盒的 最大 甜蜜度。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：price = [13,5,1,8,21,2], k = 3
     * 输出：8
     * 解释：选出价格分别为 [13,5,21] 的三类糖果。
     * 礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
     * 可以证明能够取得的最大甜蜜度就是 8 。
     */
    public boolean isOk(int t, int[] price, int k) {
        //能否price里找到k个跨度>=t的值
        int pre = 0;
        int n = price.length;
        while (k > 1) {
            int left = pre;
            int right = n;
            //找mid>=pre+t的第一个
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                int x = price[pre] + t;
                if (price[mid] < x) {
                    left = mid;
                } else {
                    right = mid;
                }
            }//取r
            if (right == n) {
                return false;
            }
            pre = right;
            k--;
        }
        return true;
    }

    public int maximumTastiness(int[] price, int k) {
        int n = price.length;
        Arrays.sort(price);
        int max = price[n - 1];
        int left = -1;
        int right = max + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (isOk(mid, price, k)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
